Tên chữ của chùa là Tư Phúc tự hay Thiên Tư Phúc Tự, trong dân gian quen gọi theo tên núi là chùa Côn Sơn hay còn gọi là Chùa Hun. Chùa nằm dưới chân núi Côn Sơn. Tương truyền đây là nơi từng diễn ra trận hỏa công hun lửa tạo khói để vây bắt Phạm Bạch Hổ thời loạn 12 sứ quân của Đinh Bộ Lĩnh ở thế kỷ 10. Nên ngoài tên gọi Côn Sơn, núi còn có tên là Kỳ Lân hay núi Hun.[6]

Sách Đại Nam Nhất Thống Chí chép về chùa Côn Sơn trong mục "Núi Côn Sơn", gắn liền với một loạt các nhân vật lịch sử nổi bật:

Năm Hưng Long thứ 12 (1304) nhà sư Pháp Loa cho xây dựng một chùa nhỏ gọi là Kỳ Lân. Đến năm Khai Hựu thứ nhất (1329) chùa được xây dựng mở rộng thành Côn Sơn Thiên Tư Phúc tự, giao cho Huyền Quang chủ trì. Ngay từ thời nhà Trần, chùa Côn Sơn là một trong ba trung tâm của thiền phái Trúc Lâm cùng với Yên Tử và Quỳnh Lâm, Quảng Ninh.[8] Ca dao có câu:

Chùa là nơi tu hành của Quốc sư Huyền Quang - vị tổ thứ ba của Thiền phái Trúc Lâm. Sau khi Huyền Quang mất, vua Trần Minh Tông đã cho xây Đăng Minh bảo tháp chứa xá lị của ông và từ đó đến nay, ngày mất của Huyền Quang dần trở thành Hội Xuân Côn Sơn.[5][9]

Sang thời Lê Sơ, chùa là nơi Nguyễn Trãi lui về ở ẩn theo gót ông ngoại mình là Trần Nguyên Đán cũng đã về Côn Sơn lánh đời cuối thời Trần. Năm 1439, vua Lê Thái Tông khôi phục lại các chức tước cho Nguyễn Trãi, trong đó ông có một chức danh là Đề cử Côn Sơn Tư Phúc tự tức là "Quản lý chùa Tư Phúc" (chùa Côn Sơn).[10][11]

Vào thời Lê trung hưng, giai đoạn Thiền sư Mai Trí Bản hiệu Pháp Nhãn trụ trì, chùa được trùng tu và mở rộng đến quy mô đồ sộ. Theo bia tạc năm Hoằng Định thứ 15 (1614), khi đó chùa có đến 83 gian, bao gồm các công trình như: tam quan, tòa Cửu phẩm liên hoa gắn 385 tượng chư Phật, nhà thiêu hương, tiền đường, thượng điện, hành lang trái phải, tạc mới tượng Quan Âm Bồ Tát nghìn mắt nghìn tay, 18 tượng Phật sơn son trên thượng điện, thếp vàng lại ba tượng tam thế... Sau nhiều năm chiến tranh tàn phá, chùa Côn Sơn chỉ còn quy mô vừa phải nhưng kiến trúc vẫn hài hòa với cảnh quan.[5][8]